{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第8章-提升方法-导读\n",
    "\n",
    "### 提升方法AdaBoost算法\n",
    "\n",
    "#### 提升方法的基本思路\n",
    "&emsp;&emsp;这一部分提出了几个概念：弱可学习、强可学习、PAC学习框架  \n",
    "\n",
    "- **PAC学习框架：**在第1章讲的泛化误差上界的定理，也就是说，可以用一个训练误差和一个小的$\\varepsilon$以一定的概率控制泛化误差。  \n",
    "- **弱可学习：**可以找到一个方法，用这个方法预测输出变量，对于分类问题，会比随机猜测的效果略好。  \n",
    "- **强可学习：**可以学习的效果很好。  \n",
    "- **提升方法的基本思路：**如果能找到一个弱可学习算法，那就可以将该算法提升为强可学习算法。\n",
    "\n",
    "&emsp;&emsp;提升方法属于集成学习中的一种，集成学习就是用一些比较简单的模型，将它们综合起来构成一个复杂的模型。  \n",
    "&emsp;&emsp;集成学习两个主要类别：序列方法、并行方法。  \n",
    "\n",
    "- **序列方法：**当我们学到一个模型，再学下一个模型时，下一个模型依赖上一个模型的结果。 \n",
    "- **并行方法：**可以同时学很多模型，这些模型之间不会相互影响。\n",
    "\n",
    "&emsp;&emsp;第8章中介绍的方法都属于序列方法，该章中首先介绍了AdaBoost算法，这个算法是一个非常重要的序列方法，提出得比较早，具有很强的理论支撑；之后就是提升树，AdaBoost主要解决二分类问题，提升树分为回归树提升方法和分类树提升方法，既可以用分类树提升方法解决多分类问题，也可以用回归树提升方法解决回归问题（当输出变量是连续变量时，该问题称为回归问题）。  \n",
    "\n",
    "#### AdaBoost算法（算法8.1）\n",
    "&emsp;&emsp;AdaBoost算法用于解决分类问题，输出变量$y \\in \\{-1, +1\\}$，当用原始数据学习完一个模型后，那这个学习的结果如何对第二个学习的模型产生影响呢？这个时候，用第一个模型的学习效果在训练数据集上的一个表现，该表现分为整体表现（如果有多个模型，第一个模型在训练数据集上的整体表现非常好，在最终的分类器加权中，整体效果越好的模型，其权重就越大）和在单个样本上的表现效果（如果在其中一个样本上表现效果好，在训练下一个模型时，就可以较少地考察表现好的样本点，更多考察表现效果差的样本点，这个就决定了在下一个模型中，每一个样本点的权重），以上就是AdaBoost的基本思路。  \n",
    "输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}$，其中$x_i \\in \\mathcal{X} \\subseteq \\textbf{R}^n, y_i \\in \\mathcal{Y} = \\{-1, +1\\}$；弱学习算法；  \n",
    "输出：最终分类器$G(x)$。  \n",
    "(1)初始化训练数据的权值分布$$D_1 = (w_{11},\\cdots,w_{1i},\\cdots,w_{1N}), \\quad w_{1i}=\\frac{1}{N}, \\quad  i = 1, 2, \\cdots, N$$\n",
    "(2)对$m=1,2,\\cdots,M$表示学习每个小分类器的过程。  \n",
    "(a)使用具有权值分布$D_m$的训练数据集学习，得到基本分类器$$G_m(x):\\mathcal{X} \\rightarrow \\{-1,+1\\}$$ \n",
    "(b)计算$G_m(x)$在训练数据集上的分类误差率（衡量模型效果）$$\\displaystyle e_m=\\sum_{i=1}^N P(G_m(x_i) \\neq y_i)=\\sum_{i=1}^N w_{mi}I(G_m(x_i) \\neq y_i)$$  \n",
    "(c)计算$G_m(x)$的系数 $$\\alpha_m=\\frac{1}{2} \\ln \\frac{1-e_m}{e_m} $$  \n",
    "(d)更新训练数据集的权值分布$$D_{m+1}=(w_{m+1,1},\\cdots,w_{m+1,i},\\cdots,w_{m+1,N}) \\\\\n",
    "w_{m+1,i}=\\frac{w_{mi}}{Z_m}\\exp (-\\alpha_m y_i G_m(x_i)), \\quad i=1, 2, \\cdots, N$$\n",
    "其中，$Z_m$是规范化因子$$\\displaystyle Z_m=\\sum_{i=1}^N w_{mi} \\exp(-\\alpha_m y_i G_m(x_i))$$\n",
    "它使$D_{m+1}$成为一个概率分布。  \n",
    "(3)构建基本分类器的线性组合$$\\displaystyle f(x)=\\sum_{m=1}^M \\alpha_m G_m(x)$$\n",
    "得到最终分类器$$\\displaystyle G(x)=\\text{sign}(f(x))=\\text{sign}\\Big( \\sum_{m=1}^M \\alpha_m G_m(x) \\Big)$$  \n",
    "&emsp;&emsp;AdaBoost算法所用的每一个基本分类器都是非常简单的模型，算法中并没有规定要使用什么样子的分类器，这个可以自己选择，只要分类器有效果就可以。  \n",
    "\n",
    "### AdaBoost算法的训练误差分析\n",
    "**定理8.1** （AdaBoost的训练误差界）AdaBoost算法最终分类器的训练误差界为$$\\frac{1}{N}\\sum_{i=1}^N I(G(x_i) \\neq y_i) \\leqslant \\frac{1}{N} \\sum_i \\exp(-y_i f(x_i)) = \\prod_m Z_m$$  \n",
    "**定理8.2** （二类分类问题AdaBoost的训练误差界）$$\\prod_{m=1}^M Z_m = \\prod_{m=1}^M [2 \\sqrt{e_m(1-e_m)}] = \\prod_{m=1}^M \\sqrt{(1-4\\gamma_m^2)} \\leqslant \\exp \\big( -2 \\sum_{m=1}^M \\gamma_m^2 \\big)$$，其中，$\\displaystyle \\gamma_m = \\frac{1}{2}-e_m$  \n",
    "&emsp;&emsp;$e_m$越小，说明当前分类器效果越好，$\\gamma_m$越大，$\\frac{1}{2}$可以看做是分类问题中，随机猜测分类结果的最大误差率。$\\gamma_m$可以解释成当前的基本分类器对于随机猜测结果的提升程度。提升程度越大，$\\gamma_m$越大，上界$\\displaystyle \\exp \\big( -2 \\sum_{m=1}^M \\gamma_m^2 \\big)$就越小，训练误差随着迭代次数的增加而越小，减小的速度是以指数速度变小的，也就是说，训练次数增多的时候，训练误差降低的速度会变快。  \n",
    "\n",
    "### AdaBoost算法的解释\n",
    "&emsp;&emsp;在本节中，将AdaBoost算法用第1章的统计学习方法的三要素分析该模型、策略、算法。\n",
    "\n",
    "\n",
    "> 问题：二分类问题  \n",
    "模型：加法模型$\\displaystyle f(x)=\\sum_{m=1}^M \\beta_m b (x;\\gamma_m)$  \n",
    "策略：损失函数为指数函数$L(y,f(x))=\\exp[-yf(x)]$  \n",
    "算法：前向分步算法\n",
    "\n",
    "&emsp;&emsp;AdaBoost从模型形式上看，该模型是一个加法模型$\\displaystyle f(x)=\\sum_{m=1}^M \\beta_m b (x;\\gamma_m)$，其中$b(x;\\gamma_m)$为基函数，该基函数可能是关于$x$的线性函数，也可能是二次函数，这个函数的形式不变，但是有一个参数$\\gamma_m$，在每一个求和项中，$\\gamma_m$是不一样的，求解该模型，$M$即求和项项数是已知的，基函数$b(x;\\gamma_m)$ 也是给定的，所要求解的就是$\\beta_m$和$\\gamma_m$。  \n",
    "&emsp;&emsp;AdaBoost的损失函数是一个指数函数$L(y,f(x))=\\exp[-yf(x)]$，二分类中$y \\in \\{-1, +1\\}, f(x) \\in \\{-1, +1\\}$，如果预测值等于真实值（预测正确即$y=f(x)$），$yf(x)=1$，损失为$e^{-1}$，如果不相等（预测错误即$y \\neq f(x)$），损失为$e$，这个与我们平常看到的损失不一致，这里即使预测正确，也是有损失的，预测错误比预测正确的损失大。 \n",
    "\n",
    "#### 前向分步算法\n",
    "输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2),\\cdots, (x_N,y_N)\\}$，损失函数$L(y,f(x))$，基函数集$\\{b(x;\\gamma)\\}$;  \n",
    "输出：加法模型$f(x)$  \n",
    "(1)初始化$f_0(x)=0$  \n",
    "(2)对$m=1,2,\\cdots,M$  \n",
    "(a)极小化损失函数$$(\\beta_m, \\gamma_m) = \\mathop{\\arg \\min} \\limits_{\\beta,\\gamma} \\sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \\beta b(x_i;\\gamma))$$  \n",
    "(b)更新$$f_m(x)=f_{m-1}(x) + \\beta_m b(x;\\gamma_m)$$  \n",
    "(3)得到加法模型$$f(x)=f_M(x)=\\sum_{m=1}^M \\beta_m b(x;\\gamma_m)$$  \n",
    "&emsp;&emsp;这样，前向分步算法将同时求解从$m=1$到$M$所有参数$\\beta_m,\\gamma_m$的优化问题简化为逐次求解各个$\\beta_m, \\gamma_m$的优化问题。\n",
    "\n",
    "\n",
    "#### 前向分步算法与AdaBoost\n",
    "&emsp;&emsp;有了模型和策略，当拟合加法模型时，需要求解很多的参数，有一个比较简单的算法（前向分步算法），已知加法模型$f(x)$由$M$项求和组成的，用迭代的方法求解$f(x)$，初始化$f_0(x)=0$，现考虑$f_1(x)=f_0(x)+\\beta_1 b(x;\\gamma_1)$，求解$\\gamma_1,\\beta_1$，使得$\\displaystyle \\gamma_1^*, \\beta_1^* = \\mathop{\\arg\\max}\\limits_{\\gamma,\\beta} \\frac{1}{N} \\sum_{i=1}^N L(y_i,f_1(x_i))$，可以得到$f_1(x)=f_0(x)+\\beta_1^* b(x;\\gamma_1^*)$，下一次更新为$f_2(x) = f_1(x) + \\beta_2 b(x;\\gamma_2)$，求解$\\beta_2, \\gamma_2$，依然利用经验风险最小这个准则，$\\displaystyle \\gamma_2^*, \\beta_2^* = \\mathop{\\arg\\max}\\limits_{\\gamma,\\beta} \\frac{1}{N} \\sum_{i=1}^N L(y_i,f_2(x_i))$，得到$f_2(x) = f_1(x) + \\beta_2^* b(x;\\gamma_2^*)$，以此类推，可以求得$f(x)=f_M(x)$。其中，每步中 得到的$b(x;\\gamma_m)$就是$G_m(x)$，$\\beta_m$就是$\\alpha_m$。  \n",
    "&emsp;&emsp;当用这样的框架重新分析AdaBoost算法之后，可以进行很多的变形，当损失函数不同，很多AdaBoost变形，都是通过替换框架中的策略得到的。\n",
    "\n",
    "### 提升树\n",
    "&emsp;&emsp;提升树与AdaBoost算法的思路是非常像的，也是考虑一个加法模型，AdaBoost算法中没有规定所用的分类器，提升树中，基本分类器为分类树或回归树（分类树用来做分类问题，回归树用来做回归问题），所用的算法依然是前向分步算法。对于分类树的提升树，如果是二分类问题，该算法和AdaBoost算法是等价的，所以本节中没有介绍分类问题的提升树算法。\n",
    "\n",
    "\n",
    "> 基本分类器：分类树或回归树  \n",
    "提升树模型：$\\displaystyle f_M(x)=\\sum_{m=1}^M T(x;\\Theta_m)$  \n",
    "前向分步算法：$$f_m(x) = f_{m-1}(x) + T(x;\\Theta_m) \\\\ \n",
    "\\hat{\\Theta}_m = \\mathop{\\arg\\max} \\sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i; \\Theta_m))$$  \n",
    "\n",
    "#### 回归问题的提升树算法\n",
    "&emsp;&emsp;提升树模型是由$M$个基本分类器构成的，每一个基本分类器都是一个回归树$T(x;\\Theta_m)$，回归树中的$\\Theta_m$都包含了哪些项？首先对应了一个空间上的划分（每一个叶子结点），还包括了每一个叶子结点的拟合值$c$，对于前向分步算法，首先初始化$f_0(x)=0$，考察加法模型的第一项$f_1(x) = f_0(x) + T(x;\\Theta_1)$，求解$\\Theta_1$采用最小化经验风险$\\displaystyle \\frac{1}{N} \\sum_{i=1}^N L(y_i, f_1(x_i))$，对于提升树，一般采用平方误差损失$L(y,f(x))=(y-f(x))^2$\n",
    "\n",
    "> 算法8.3（回归问题的提升树算法-平方误差损失）  \n",
    "输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}, x_i \\in \\mathcal{X} \\subseteq \\text{R}^n, y_i \\in \\mathcal{Y} \\subseteq \\text{R}$  \n",
    "输出：提升树$f_M(x)$  \n",
    "(1)初始化f_0(x)=0  \n",
    "(2)对$m=1,2,\\cdots,M$  \n",
    "(a)计算残差$r_{mi}=y_i-f_{m-1}(x_i), i=1,2,\\cdots,N$  \n",
    "(b)拟合残差$r_{mi}$学习一个回归树，得到$T(x;\\Theta_m)$  \n",
    "(c)更新$f_m(x) = f_{m-1}(x) + T(x; \\Theta_m)$  \n",
    "(3)得到回归问题提升树$$f_M(x)=\\sum_{m=1}^M T(x;\\Theta_m)$$\n",
    "\n",
    "#### 对算法8.3的解释\n",
    "&emsp;&emsp;首先初始化$f_0(x)=0$，对于第1棵树直接拟合得到$y,f_0(x)$，通过最小化$y_i$和$f_0(x_i)$的平方误差损失求解$\\Theta_1$，然后得到回归树模型$T(x;\\Theta_1)$，用训练数据集训练，求出预测值，通过预测值和真实值计算每一个样本点上的残差$r_1$，当求解下一个棵树时，直接用残差$r_{1,i}$学习回归树（即残差$r_1$为$y$），继续用$r_1$和$f_1(x)$的平方误差损失最小求解$\\Theta_2$，得到第2棵树$T(x;\\Theta_2)$，目前有了一个新的模型$f_2(x)=T(x;\\Theta_1)+T(x;\\Theta_2)$，继续计算残差，然后拟合第3棵树，最终得到第M棵树$f_M(x)$。  \n",
    "&emsp;&emsp;为什么这里是通过拟合残差来学习回归树呢？书中也给出了推导，对于任意一个样本点，$y$和$f(x)$拟合之间的损失为$L(y,f(x))=(y-f(x))^2$，在前向分步算法中，第$M$步得到的$f_m(x)=y-f_{m-1}(x)+T(x;\\Theta_m)$  \n",
    "$\\begin{array}{lll} \n",
    "\\therefore & {} & L(y,f(x)) \\\\\n",
    "& = & \\big[y-f_{m-1}(x) - T(x;\\Theta_m)\\big]^2 \\\\\n",
    "& = & [r_{m-1} - T(x;\\Theta_m)]^2 \\\\\n",
    "& = & L(r_{m-1}, T(x;\\Theta_m))\n",
    "\\end{array}$  \n",
    "&emsp;&emsp;最小化$L(y, f_{m-1}(x) + T(x;\\Theta_m))$时，相当于最小化$L(r_{m-1}, T(x;\\Theta_m))$，所以用整体样本中$y$和$f_m(x)$的经验风险最小化等价于用上一步残差$r_{m-1}$拟合第$M$步的回归树，可求解出$\\Theta_m$，$\\Theta_m$包含两个部分：空间的划分（每一个叶子结点）和每一个叶子结点上的拟合值$c$。  \n",
    "\n",
    "#### 梯度提升算法\n",
    "&emsp;&emsp;假如不用平方误差损失，换成其他的损失函数时，残差不好计算，这个时候就可以用新的提升算法（算法8.4——梯度提升算法），梯度提升算法依然采用拟合每一个训练数据，由于不是采用平方误差损失，之前用残差拟合下一棵树的方法就不适用了，就替换为下面的算法。  \n",
    "\n",
    "> 算法8.4（梯度提升算法）  \n",
    "输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2), \\cdots, (x_N,y_N)\\}, x \\in \\mathcal{X} \\subseteq \\text{R}^n, y \\in \\mathcal{Y} \\subseteq \\text{R}$，损失函数$L(y,f(x))$  \n",
    "输出：回归树$\\hat{f}(x)$  \n",
    "(1)初始化$\\displaystyle f_0(x)= \\mathop{\\arg \\min} \\limits_{c} \\sum_{i=1}^N L(y_i, c)$  \n",
    "(2)对$m=1,2,\\cdots,M$\n",
    "(a)对$i=1,2,\\cdots,N$，计算$$r_{mi}=-\\big[\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)} \\big]_{f(x)=f_{m-1}(x)}$$\n",
    "(b)对$r_{mi}$拟合一个回归树，得到第$m$棵树的叶结点区域$\\text{R}_{mj},j=1,2,\\cdots,J$  \n",
    "(c)对$j=1,2,\\cdots,J$，计算$$c_{mj}=\\mathop{\\arg \\min} \\limits_{c} \\sum_{x_i \\in \\text{R}_{mj}} L(y_i, f_{m-1}(x_i) + c)$$\n",
    "(d)更新$\\displaystyle f_m(x)=f_{m-1}(x) + \\sum_{j=1}^J c_{mi} I(x \\in \\text{R}_{mj})$  \n",
    "(3)得到回归树$$\\hat{f}(x) = f_M(x)=\\sum_{m=1}^M \\sum_{j=1}^J c_{mj}I(x \\in \\text{R}_{mj})$$\n",
    "\n",
    "&emsp;&emsp;在算法中，依然是需要一个类似与残差的变量，该值（$r_{mi}$）是用负梯度计算的，$r_{mi}$是损失函数关于$f(x)$的负梯度，然后用$r_{mi}$拟合新的回归树，一般情况下是求解$\\Theta_m$，$\\Theta_m$包含两个部分：空间上的划分$\\text{R}_{mj},j=1,2,\\cdots,J$和拟合值$c_{mj}$。  \n",
    "&emsp;&emsp;这里就有两个问题：\n",
    "1. 为什么可以用负梯度近似代替残差？\n",
    "2. 计算残差时，为什么只能通过残差求解$\\Theta_m$的第1部分$\\text{R}_{mj}$，第1部分还需要重新计算？  \n",
    "\n",
    "**解答：** 假设$L(y_i,f(x_i))=[y_i-f(x_i)]^2$，则$\\displaystyle -\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)} = -(-2[y_i-f(x_i)]) = 2[y_i-f(x_i)] = r_{mi}$，推广用到的是一阶泰勒展开的近似，从平方损失的例子中可以看到，用负梯度确实可以代替残差。但是在推导的过程中，可以看到前面有一个系数2，所以负梯度只是残差的代替，并不能等同于残差。这也就是为什么在(c)步中要根据原始的$y_i$和$f(x)$的形式求解$c$   \n",
    "&emsp;&emsp;由于已经确定了每一个叶子结点区域$\\text{R}_{mj}$，对于每一个叶子结点$j$，只需要考虑该叶子结点，而不需要考虑其他的叶子结点，当求这一个叶子结点（即求分到这个叶子结点的样本点$x_i \\in \\text{R}_{mj}$）中的样本点$x_i$，求这些点的经验损失和（$\\text{R}_{mj}$上对应样本点的经验风险），真实值为$y_i$，拟合值为$f_{m-1}(x_i)$再加上第$m$步中得到的数，这里只关心$\\text{R}_{mj}$区域中的叶子结点部分，对于这个叶子结点，新得到的这个数（拟合值）为$c$，所以整体的拟合值为$f_{m-1}(x_i)+c$。  \n",
    "&emsp;&emsp;通过经验风险最小，求得这个叶子结点上那棵新树对应的$c$值，$f_m(x_i)+c$表示为在$\\text{R}_{mj}$区域范围的样本点的拟合值$f_m(x_i)$。所以对于一个新的回归树，已经求了$J$（第$m$棵树中叶子结点的个数）个这样的$c$，更新的形式为$\\displaystyle f_m(x)=f_{m-1}(x)+ \\sum_{j=1}^J c_{mj} I(x \\in \\text{R}_{mj})$，对于每个样本点，只在其中的一个指示函数（indicator function）中等于1，因为只能属于其中的一个$\\text{R}_{mj}$，当$I(x \\in \\text{R}_{mj})=1$时，才累积求和。对于每一棵树$f_m(x)$，都有一个$c_m$，对于每一棵树上，又划分了$J$个区域，所以拟合值为$c_{mj}$。对于 每一个样本点，在每一棵树上，都只有一个指示函数为1，虽然(3)步求和是$M,J$，但是最后求解时，只有$M$项的和。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
